#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;

struct edge{
	int a, b, c ,f;
};
const int maxn = 5010;
int p[maxn], d[maxn];
int n, s, t;
vector< vector<int> > g;
vector<edge> e;

#define inf 1e9

void newedge(int a, int b, int c){
	edge cur = {a, b, c, 0};
	int sz = e.size();
	g[a].push_back(sz);
	e.push_back(cur);
	cur.c = 0;
	swap(cur.a, cur.b);
	g[b].push_back(sz + 1);
	e.push_back(cur);
}
bool bfs() {
	queue<int> q;
	q.push(s);
	memset (d, -1, sizeof d);
	d[s] = 0;
	while (!q.empty() &&  d[t] == -1) {
		int v = q.front();
		q.pop();
		for (int i=0; i<g[v].size(); ++i) {
			int id = g[v][i], u = e[id].b;
			if (d[u] == -1 && e[id].f < e[id].c) {
				q.push(u);
				d[u] = d[v] + 1;
			}
		}
	}
	return d[t] != -1;
}

long long dfs (int v, int flow) {
	if (!flow)  return 0;
	if (v == t)  return flow;
	long long ret = 0;
	for (; p[v]<g[v].size(); ++p[v]) {
		int id = g[v][p[v]],
			u= e[id].b;
		if (d[u] != d[v] + 1)  continue;
		long long cur = dfs (u, min (flow, e[id].c - e[id].f));
		e[id].f += cur;
		e[id^1].f -= cur;
		flow -= cur;
		ret += cur;
		if (!flow){
			return ret;
		}
	}
	return ret;
}

long long dinic() {
	long long ans = 0;
	while(bfs()){
		memset (p, 0, sizeof p);
		while (long long cur = dfs (s, inf))
			ans += cur;
	}
	return ans;
}